<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【区间DP练习】洛谷 P1880[NOI1995]石子合并 P1063能量项链P2654 原核生物培养.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  洛谷 P1880[NOI1995]石子合并 https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;pr">
<meta property="og:type" content="article">
<meta property="og:title" content="【区间DP练习】洛谷 P1880[NOI1995]石子合并 P1063能量项链P2654 原核生物培养.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90%E5%8C%BA%E9%97%B4DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1880[NOI1995]%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%20P1063%E8%83%BD%E9%87%8F%E9%A1%B9%E9%93%BEP2654%20%E5%8E%9F%E6%A0%B8%E7%94%9F%E7%89%A9%E5%9F%B9%E5%85%BB/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  洛谷 P1880[NOI1995]石子合并 https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;pr">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:25:28.314Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="DP">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【区间DP练习】洛谷 P1880[NOI1995]石子合并 P1063能量项链P2654 原核生物培养" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E5%8C%BA%E9%97%B4DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1880%5BNOI1995%5D%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%20P1063%E8%83%BD%E9%87%8F%E9%A1%B9%E9%93%BEP2654%20%E5%8E%9F%E6%A0%B8%E7%94%9F%E7%89%A9%E5%9F%B9%E5%85%BB/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【区间DP练习】洛谷 P1880[NOI1995]石子合并 P1063能量项链P2654 原核生物培养.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p1880noi1995石子合并"><a class="markdownIt-Anchor" href="#洛谷-p1880noi1995石子合并"></a> 洛谷 P1880[NOI1995]石子合并</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1880">https://www.luogu.com.cn/problem/P1880</a><br />
环形的石子合并，可以把环形拆开，在末尾接一份自己的复制当线形来做<br />
dp数组也需要在右端外接一份自己的复制<br />
犯错：<br />
因为dp公式会访问到j+1的下标，，刚开始用的if(j&gt;=n)判断越界 ，在j=n-1时会访问到下标为n的位置导致越界，所以一直出错<br />
应该改为if(j+1&gt;=n)</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 105;<br />
int n,qu[N],dx[N][N&lt;&lt;1],dn[N][N&lt;&lt;1],sum[N&lt;&lt;1];</p>
<pre><code>int main()
&#123;
   memset(dn,1,sizeof(dn));

   std::cin &gt;&gt;n;
   for(int i=0; i&lt;n; i++)&#123;
      std::cin &gt;&gt; qu[i];
   &#125;

   for(int i=1; i&lt;n; i++)&#123;
      sum[i] = sum[i-1] + qu[i];
   &#125;
   for(int i=0; i&lt;n; i++)&#123;
      sum[n+i] = sum[n+i-1] + qu[i];
   &#125;
   for(int i=0; i&lt;n; i++)&#123;
      dn[i][i] = 0;
   &#125;
   for(int i=1; i&lt;n; i++)&#123;
      for(int st=0; st&lt;n; st++)&#123;
         int ed = st+i;
         for(int j=st; j&lt;ed; j++)&#123;
            int gain = sum[ed]-sum[st]+qu[st];
            if(j+1&gt;=n)&#123;
               dn[st][ed] = std::min(dn[st][ed],dn[st][j]+dn[j-n+1][ed-n]+gain);
               dx[st][ed] = std::max(dx[st][ed],dx[st][j]+dx[j-n+1][ed-n]+gain);
            &#125;else&#123;
               dn[st][ed] = std::min(dn[st][ed],dn[st][j]+dn[j+1][ed]+gain);
               dx[st][ed] = std::max(dx[st][ed],dx[st][j]+dx[j+1][ed]+gain);
            &#125;
         &#125;
      &#125;
   &#125;
   int mx=0,mn=1e7;
   for(int i=0; i&lt;n; i++)&#123;
      mx = std::max(dx[i][n-1+i],mx);
      mn = std::min(dn[i][n-1+i],mn);
   &#125;
   std::cout &lt;&lt; mn &lt;&lt; std::endl &lt;&lt; mx &lt;&lt;std::endl;
   return 0;
&#125;
</code></pre>
<p>​</p>
<h2 id="洛谷-p1063-能量项链"><a class="markdownIt-Anchor" href="#洛谷-p1063-能量项链"></a> 洛谷 P1063 能量项链</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1063">https://www.luogu.com.cn/problem/P1063</a><br />
同样时环形类石子合并dp<br />
刚开始dp公式dp[st][ed] =<br />
std::max(dp[st][ed],dp[st][j]+dp[j+1-n][ed-n]+gain);中的dp[j+1-n][ed-n]写成了dp[j+1-n][ed]，当场暴毙</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 105;<br />
LL n,qu[N&lt;&lt;1],dp[N][N&lt;&lt;1];</p>
<pre><code>int main()
&#123;
   std::cin &gt;&gt; n;
   for(int i=1; i&lt;=n; i++)&#123;
      std::cin &gt;&gt;qu[i];
      qu[i+n] = qu[i];
   &#125;
   qu[n&lt;&lt;1|1] = qu[1];
   for(int i=1; i&lt;n; i++)&#123;
      for(int st=1; st&lt;=n; st++)&#123;
         int ed = st+i;
         for(int j=st; j&lt;ed ;j++)&#123;
            int gain = qu[st]*qu[j+1]*qu[ed+1];
            if(j+1&gt;n)&#123;
               dp[st][ed] = std::max(dp[st][ed],dp[st][j]+dp[j+1-n][ed-n]+gain);
            &#125;else&#123;
               dp[st][ed] = std::max(dp[st][ed],dp[st][j]+dp[j+1][ed]+gain);
            &#125;
         &#125;
      &#125;
   &#125;
   LL mx = -1;
   for(int i=0; i&lt;n; i++)&#123;
      mx = std::max(mx,dp[1+i][n+i]);
   &#125;
   std::cout &lt;&lt; mx &lt;&lt; std::endl;

   return 0;
&#125;
</code></pre>
<p>​</p>
<p>上面这个思路开了2倍的dp空间。下面改一个开4倍dp空间的（与线形区间合并更加相似）<br />
只需要把st的限制条件从st&lt;=n 改成st&lt;=(n&lt;&lt;1)-i (-i保证下标不越界)，再把循环里面判断j+1&gt;n的分支去掉就可以了</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 105;<br />
LL n,qu[N&lt;&lt;1],dp[N&lt;&lt;1][N&lt;&lt;1];</p>
<pre><code>int main()
&#123;
   std::cin &gt;&gt; n;
   for(int i=1; i&lt;=n; i++)&#123;
      std::cin &gt;&gt;qu[i];
      qu[i+n] = qu[i];
   &#125;
   qu[n&lt;&lt;1|1] = qu[1];
   for(int i=1; i&lt;n; i++)&#123;
      for(int st=1; st&lt;=(n&lt;&lt;1)-i; st++)&#123;
         int ed = st+i;
         for(int j=st; j&lt;ed ;j++)&#123;
            int gain = qu[st]*qu[j+1]*qu[ed+1];
               dp[st][ed] = std::max(dp[st][ed],dp[st][j]+dp[j+1][ed]+gain);
         &#125;
      &#125;
   &#125;
   LL mx = -1;
   for(int i=0; i&lt;n; i++)&#123;
      mx = std::max(mx,dp[1+i][n+i]);
   &#125;
   std::cout &lt;&lt; mx &lt;&lt; std::endl;

   return 0;
&#125;
</code></pre>
<p>​</p>
<h2 id="洛谷-p2654-原核生物培养"><a class="markdownIt-Anchor" href="#洛谷-p2654-原核生物培养"></a> 洛谷 P2654 原核生物培养</h2>
<p>很显然（真的很显然）是优先队列+区间dp，别忘了每次dp完之后还要往队列里面push一个<br />
题目让求最小值，一开始一直再求max，差点WA傻了</p>
<p>​<br />
#include <iostream><br />
#include <cstdio><br />
#include <algorithm><br />
#include <queue><br />
#include <map><br />
#include <stack><br />
#include <string><br />
#include <cstring><br />
#include <vector><br />
#include <cmath><br />
#include <set><br />
typedef long long int LL;<br />
const int N = 1e4+5,M=11,INF = 0x7fffffff;<br />
int dp[M][M&lt;&lt;1],pos[M],qu[M],sum[M&lt;&lt;1];<br />
std::priority_queue&lt;int,std::vector<int>,std::greater<int> &gt; q;<br />
int n,m,k,v;<br />
LL ans;<br />
int main()<br />
{<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;k);<br />
for(int i=0; i&lt;n; i++){<br />
scanf(&quot;%d&quot;,&amp;v);<br />
q.push(v);<br />
}<br />
while(k–){<br />
for(int i=1; i&lt;=m; i++) for(int j=1; j&lt;=(m&lt;&lt;1); j++) dp[i][j] = INF;<br />
for(int i=1; i&lt;=m; i++){<br />
scanf(&quot;%d&quot;,&amp;pos[i]);<br />
}<br />
for(int i=1; i&lt;=m; i++){<br />
qu[pos[i]] = q.top();<br />
q.pop();<br />
}<br />
for(int i=1; i&lt;=m; i++) sum[i] = sum[i-1]+qu[i];<br />
for(int i=1; i&lt;=m; i++) sum[i+m] = sum[i+m-1]+qu[i];<br />
for(int i=1; i&lt;=m; i++) dp[i][i] = 0;<br />
for(int i=1; i&lt;m; i++){<br />
for(int st=1; st&lt;=m; st++){<br />
int ed = st+i;<br />
for(int j=st; j&lt;ed; j++){<br />
if(j+1&gt;m) dp[st][ed] = std::min(dp[st][ed],dp[st][j]+dp[j+1-m][ed-m]+sum[ed]-sum[st-1]);<br />
else dp[st][ed] = std::min(dp[st][ed],dp[st][j]+dp[j+1][ed]+sum[ed]-sum[st-1]);<br />
}<br />
}<br />
}<br />
int mx = INF;<br />
for(int i=1; i&lt;=m; i++){<br />
mx = std::min(mx,dp[i][m+i-1]);<br />
}<br />
ans += mx;<br />
q.push(sum[m]);<br />
}<br />
printf(&quot;%lld&quot;,ans);<br />
return 0;<br />
}</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E5%8C%BA%E9%97%B4DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1880[NOI1995]%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%20P1063%E8%83%BD%E9%87%8F%E9%A1%B9%E9%93%BEP2654%20%E5%8E%9F%E6%A0%B8%E7%94%9F%E7%89%A9%E5%9F%B9%E5%85%BB/" data-id="cl2uhoec7001me4j3daxt0m22" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%20spfa%20Dijkstra%E3%80%91%20_%20%E6%B4%9B%E8%B0%B7%20P3371%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%EF%BC%88%E5%BC%B1%E5%8C%96%E7%89%88%EF%BC%89_%20##%20lguou/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【单源最短路 spfa Dijkstra】 _ 洛谷 P3371 【模板】单源最短路径（弱化版）_
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95%E3%80%91python%20matplotlib%20%E8%87%AA%E5%AD%A6%E5%85%A5%E9%97%A8%EF%BC%88%E9%9A%8F%E7%BC%98%E6%9B%B4%E6%96%B0%EF%BC%89/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【学习记录】python matplotlib 自学入门（随缘更新）.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>